/**
 *  \file linklist.c
 *  \author ChenJR
 */
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 50
#define FORWARD(x) (x) =(x)->next

typedef enum STATUS {
    OK,
    ERROR,
    INFEASIBLE,
    OVERFLOW,
    INVALID_ARGUMENT
} Status;

typedef struct {
    int a;
    int  n;
} polynode;

typedef struct  LNode {
    polynode data;
    struct  LNode *next;

} LNode, *LinkList;


void  OutputList( LinkList l );
Status DestoryList( LinkList list );
LNode* CreateNode( polynode n, LNode* next );
Status InsertNode( LNode* nowNode, LNode* newNode );
Status RemoveNode( LNode * pre );


void OutputList( LinkList l ) {
    LinkList head = l;
    if( l == NULL|| l->next ==NULL ) {
        printf( "0 0\n" );

        return;
    }
    l = l->next;
    if(l)
#ifdef DEBUG
    printf( "%dx^%d ", l->data.a, l->data.n );

#else
    printf( "%d %d", l->data.a, l->data.n );
#endif
    l = l->next;
    while ( l  ) {
#ifdef DEBUG
        printf( "+ %dX^%d ", l->data.a, l->data.n );
#else
        printf( " %d %d", l->data.a, l->data.n );
#endif
        l = l->next;
    };
    putchar( '\n' );

}

LNode* CreateNode( polynode n, LNode* next ) {
    LNode* pNode = ( LNode* )malloc( sizeof( LNode ) );
    pNode->data = n;
    pNode->next = next;
    return pNode;

}
Status DestoryList( LinkList list ) {
    LinkList p = list;
    LinkList t;
    while( p ) {
        t = p;
        p = p->next;
        free( t );
    }
    return OK;
}
/*insert node new into list after node now*/
Status InsertNode( LNode* nowNode, LNode* newNode ) {
    newNode->next = nowNode->next;
    nowNode->next = newNode;
    return OK;
}
/*remove node after pre*/
Status RemoveNode( LNode * pre ) {
    if( ( pre == NULL ) || ( pre->next == NULL ) )return ERROR;
    LNode* t = pre->next;
    pre->next = t->next;
    free( t );
    return OK;
}

Status BuildPoly( LNode * l ) {
    if( !l )return INVALID_ARGUMENT;
    LNode* h = l;
    int num = 0;
    int a, n;
    a = n = 0;
    polynode t;
    scanf( "%d", &num );
    while( num-- ) {
        scanf( "%d %d", &a, &n );
        t.a = a;
        t.n = n;
        l->next = CreateNode( t, NULL ) ;
        FORWARD( l );
        // InsertNode( h, CreateNode( t, NULL ) );
    }
    return OK;
}

LNode* Add( LNode* L1, LNode*L2 ) {
    LNode* Head, *L;
    polynode t = {0};
    LNode* H1 = L1;
    LNode*   H2 = L2;
    L = CreateNode( t, NULL );
    Head = L;
    L1 = L1->next;
    L2 = L2->next;
    while( L1 && L2 ) {
        if( L1->data.n == L2->data.n ) {
            t .a = L1->data.a + L2->data.a;
            t.n = L1->data.n;
            FORWARD( L1 );
            FORWARD( L2 );
            if( t.a != 0 )
                L->next = CreateNode( t, NULL );

        } else if( L1->data.n > L2->data.n ) {
            L->next = CreateNode( L1->data, NULL );
            FORWARD( L1 );
        } else if( L1->data.n < L2->data.n ) {
            L->next = CreateNode( L2->data, NULL );
            FORWARD( L2 );
        }
        if( L->next )

            FORWARD( L );
    }
    while( L1 ) {
        L->next = CreateNode( L1->data, NULL );
        FORWARD( L1 );
        FORWARD( L );
    }
    while ( L2 ) {
        L->next = CreateNode( L2->data, NULL );
        FORWARD( L2 );
        FORWARD( L );
    }
    return Head;
}


LNode* Multi( LNode* L1, LNode* L2 ) {
    polynode t = {0};
    LNode* L = CreateNode( t, NULL );
    LNode* Head = L;
    LNode* L_old = NULL;
    LNode*   H1 = L1;
    LNode*   H2 = L2;
    L1 = L1->next;
    L2 = L2->next;
    LNode* tempL = CreateNode( t, NULL );
    LNode* HtempL = tempL;
    while( L1 ) {
        L2 = H2->next;
        tempL = HtempL;
        while( L2 ) {
            t.a = ( L1->data.a ) * ( L2->data.a );
            t.n = ( L1->data.n ) + ( L2->data.n );
            tempL->next = CreateNode( t, NULL );
            FORWARD( tempL );

            FORWARD( L2 );
        }//while( L2 )
        FORWARD( L1 );
        L_old = L;
        L = Add( L_old, HtempL );
        DestoryList( L_old );
        DestoryList( HtempL->next );
        L_old = NULL;


    }//while( L1 )

    return L;
}//Multi( LNode* L1, LNode*L2 )

int main() {
    polynode t = {0};
    LNode* L1 = CreateNode( t, NULL );
    LNode* L2 = CreateNode( t, NULL );
    BuildPoly( L1 );
    BuildPoly( L2 );
#ifdef DEBUG
    printf( "What you input is:\n" );
    OutputList( L1 );
    OutputList( L2 );
    putchar('\n');
#endif
    LNode*   L_multi = Multi( L1, L2 );
    OutputList( L_multi );
    LNode* L_add = Add( L1, L2 );
    OutputList( L_add );

    DestoryList( L1 );
    DestoryList( L2 );
    DestoryList( L_add );
    DestoryList( L_multi );
    return 0;
}
